package com.sort;

import utils.CreateArr;

/**
 * 1)
 * [选择排序] :小到大排序
 * 1.遍历所有未排序的元素,找到最小的那个元素
 * 2.将这个元素与未排序序列的第一个元素交换位置
 * 3.当剩下一个元素时,排序结束
 * O(n*n)
 */
public class SelectionSort {

    static int[] selectionSort(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;   //是最小值初始化为待排数组的第一个元素的下标
            for (int j = i; j < arr.length; j++) {   //找到[i,n)中的最小值
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            /*已经找到最小值,现在要执行第二步,交换 min 与 arr[i] 的值*/
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
        return arr;
    }

    public static void main(String[] args) {
        //这里 CreateArr
        int[] arr = selectionSort(CreateArr.createRandomInt(20, 5, 1000));

        System.out.print("\n排序后 : ");
        for (int i : arr) {
            System.out.print(" " + i);
        }
    }
}
